﻿// 0803train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <cmath>
#include <limits.h>
#include <queue>

using namespace std;


/*
题目描述
给你一个字符串s,首尾相连成一个环形,请你在环中找出o字符出现了偶数次最长子字符串的长度。

输入描述
输入由一个小写字母组成的字符串s
1 <= s.lenth <= 5x10^5

输出描述
输出是一个整数

输入
alolobo

输出
6
最长子字符串之一是alolob,它包含2个o


输入
looxdolx

输出
7
最长子字符串oxdolxl,由于是首尾连接一起的,
所以最后一个x和开头的l是连接在一起的此字符串包含2个o
 */

void solve01(string&oh_str)
{
    int o_max_count = 0;
    vector<int>o_index_vec;
    int str_size = oh_str.size();

    for (int i=0; i<oh_str.size(); i++)
    {
        char oh_char = oh_str[i];
        if (oh_char=='o')
        {
            o_index_vec.push_back(i);
            o_max_count += 1;
        }
    }

    if (o_max_count%2==0)
    {
        cout << oh_str.size();
        return;
    }
    int result = oh_str.size()-1;

    cout << result;
    //solve01
}


/*
 均衡串定义:
 字符串只包含两种字符，且两种字符的个数相同。
给定一个均衡字符串，请给出可分割成新的均衡子串的最大个数。
约定字符串中只包含大写的X和Y两种字符。

输入描述
均衡串: XXYYXY
字符串的长度[2,10000]。给定的字符串均为均衡串。

输出描述
输出一个数字，表述可分割成新的均衡子串的最大个数。
如上述例子可分割为两个子串，XXYY和XY，输出答案为2。

输入
XXYYXY

输出
2
 */
void solve02(string&oh_str)
{
    char target_char = oh_str[0];
    int curr_count = 1;

    int result = 0;
    int vec_size = oh_str.size();
    for (int i=1; i< vec_size; i++)
    {
        char curr_char = oh_str[i];
        if (curr_char==target_char)
        {
            curr_count += 1;
        }
        else
        {
            curr_count -= 1;
        }
        if (curr_count==0)
        {
            result += 1;
        }
        //for------
    }
    cout << result;
    //solve02------
}


/*
 示例 1：

输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

示例 2：

输入：s = "RLRRRLLRLL"
输出：2
解释：s 可以分割为 "RL"、"RRRLLRLL"，每个子字符串中都包含相同数量的 'L' 和 'R' 。
注意，s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。

示例 3：

输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR" 。
 */

int balancedStringSplit(string s) {

    string oh_str = s;
    char target_char = oh_str[0];
    int curr_count = 1;

    int result = 0;
    int vec_size = oh_str.size();
    for (int i = 1; i < vec_size; i++)
    {
        char curr_char = oh_str[i];
        if (curr_char == target_char)
        {
            curr_count += 1;
        }
        else
        {
            curr_count -= 1;
        }
        if (curr_count == 0)
        {
            result += 1;
        }
        //for------
    }
    return result;
    //------
}


/*
 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

 */

//s = "abcabcbb"
int solve03(string&oh_str)
{
    int left_index = 0;
    int str_size = oh_str.size();
    int max_length = 0;

    unordered_set<int>oh_set;

    for (int i=0; i<str_size;i++)
    {
        char curr_char = oh_str[i];
        if (!oh_set.count(curr_char))
        {
            oh_set.insert(curr_char);
            max_length = max(max_length, i - left_index + 1);
        }
        else
        {
            //常错！！！
            //只有找得到，就要一直抹左边的数
            while (oh_set.count(curr_char))
            {
                oh_set.erase(oh_str[left_index]);
                left_index += 1;
            }

            oh_set.insert(curr_char);
        }
        //for------
    }

    return max_length;
    //solve03
}


/*
 给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组
[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。
如果不存在符合条件的子数组，返回 0 。

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

输入：target = 4, nums = [1,4,4]
输出：1

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
 */

int solve04(int target, vector<int>&oh_vec)
{
    queue<int>slider_queue;

    int sum = 0;

    int min_length = INT_MAX;
    int vec_size = oh_vec.size();
    for (int i=0; i<vec_size; i++)//target = 213, nums=[12,28,83,4,25,26,25,2,25,25,25,12]
    {
        int curr_num = oh_vec[i];
    	sum += curr_num;

        slider_queue.push(curr_num);
        
    	while (sum>=target)
    	{
    		int vec_size = slider_queue.size();
    		min_length = min(min_length, vec_size);

            int front_num = slider_queue.front();
            sum -= front_num;
            slider_queue.pop();
    	}
        
    }

    if (min_length==INT_MAX)
    {
        return 0;
    }
    return min_length;
    //solve04
    //------
}

int solve14(int target, vector<int>& oh_vec)
{
    vector<int>slider_vec;

    int sum = 0;

    int min_length = INT_MAX;
    int vec_size = oh_vec.size();
    for (int i = 0; i < vec_size; i++)//target = 213, nums=[12,28,83,4,25,26,25,2,25,25,25,12]
    {
        int curr_num = oh_vec[i];
        sum += curr_num;

        slider_vec.push_back(curr_num);

        while (sum >= target)
        {
            int vec_size = slider_vec.size();
            min_length = min(min_length, vec_size);

            int front_num = slider_vec[0];
            cout << "front_num " << front_num << endl;
            sum -= front_num;
            slider_vec.erase(slider_vec.begin());
        }

    }

    if (min_length == INT_MAX)
    {
        return 0;
    }
    return min_length;
    //solve04
    //------
}


int main()
{
	{
        //target = 213, nums=[12,28,83,4,25,26,25,2,25,25,25,12]
        //target = 11, nums = [1,1,1,1,1,1,1,1]
        //target = 7, nums = [2,3,1,2,4,3]
        int target = 213;
        vector<int>nums = { 12,28,83,4,25,26,25,2,25,25,25,12 };
        cout << solve14(target, nums);

        return 0;
	}

	{
        //abcabcbb
        //pwwkew
        string oh_str = "pwwkew";
        cout << solve03(oh_str);

        return 0;
	}

	{
        //RLRRLLRLRL 4
        string oh_str = "RLRRLLRLRL";
        cout << balancedStringSplit(oh_str);
        return 0;
	}

	{
		//XXYYXY
        string oh_str;
        cin >> oh_str;
        //string oh_str = "XXYYXY";
        solve02(oh_str);
        return 0;
	}


   //
    //string oh_str = "bcbcbc";
    string oh_str;
    cin >> oh_str;
    solve01(oh_str);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
